|
In graph theory, a haven is a certain type of function on sets of vertices in an undirected graph. If a haven exists, it can be used by an evader to win a pursuit-evasion game on the graph, by consulting the function at each step of the game to determine a safe set of vertices to move into. Havens were first introduced by as a tool for characterizing the treewidth of graphs.〔 Their other applications include proving the existence of small separators on minor-closed families of graphs,〔 and characterizing the ends and clique minors of infinite graphs.〔.〕〔.〕 ==Definition== If ''G'' is an undirected graph, and ''X'' is a set of vertices, then an ''X''-flap is a nonempty connected component of the subgraph of ''G'' formed by deleting ''X''. A haven of order ''k'' in ''G'' is a function ''β'' that assigns an ''X''-flap ''β''(''X'') to every set ''X'' of fewer than ''k'' vertices. This function must also satisfy additional constraints which are given differently by different authors. The number ''k'' is called the ''order'' of the haven.〔.〕 In the original definition of Seymour and Thomas,〔.〕 a haven is required to satisfy the property that every two flaps ''β''(''X'') and ''β''(''Y'') must touch each other: either they share a common vertex or there exists an edge with one endpoint in each flap. In the definition used later by Alon, Seymour, and Thomas,〔 havens are instead required to satisfy a weaker monotonicity property: if , and both ''X'' and ''Y'' have fewer than ''k'' vertices, then . The touching property implies the monotonicity property, but not necessarily vice versa. However, it follows from the results of Seymour and Thomas〔 that, in finite graphs, if a haven with the monotonicity property exists, then one with the same order and the touching property also exists. Havens with the touching definition are closely related to brambles, families of connected subgraphs of a given graph that all touch each other. The order of a bramble is the minimum number of vertices needed in a set of vertices that hits all of the subgraphs in the family. The set of flaps ''β''(''X'') for a haven of order ''k'' (with the touching definition) forms a bramble of order at least ''k'', because any set ''Y'' of fewer than ''k'' vertices fails to hit the subgraph ''β''(''Y''). Conversely, from any bramble of order ''k'', one may construct a haven of the same order, by defining ''β''(''X'') (for each choice of ''X'') to be the ''X''-flap that includes all of the subgraphs in the bramble that are disjoint from ''X''. The requirement that the subgraphs in the bramble all touch each other can be used to show that this ''X''-flap exists, and that all of the flaps ''β''(''X'') chosen in this way touch each other. Thus, a graph has a bramble of order ''k'' if and only if it has a haven of order ''k''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Haven (graph theory)」の詳細全文を読む スポンサード リンク
|